package com.emeraldparser.util;

import java.util.Collection;
import java.util.Collections;

import com.google.common.base.Function;
import com.google.common.base.Functions;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;

public class Automatons {

	public static <V, E> Collection<Path<V, E>> pathsFrom(Automaton<? extends V, ? extends E> automaton, V source) {
		Automaton<V, E> newAutomaton = Automatons.create(automaton);
		newAutomaton.getStartVertices().clear();
		newAutomaton.addStartVertex(source);
		
		return newAutomaton.getPaths();
	}

	public static <V, E> Collection<Path<V, E>> pathsTo(Automaton<? extends V, ? extends E> automaton, V destination) {
		Automaton<V, E> newAutomaton = Automatons.create(automaton);
		newAutomaton.getAcceptVertices().clear();
		newAutomaton.addAcceptVertex(destination);
		
		return newAutomaton.getPaths();
	}

	public static <V, E> Automaton<V, E> invert(final Automaton<V, E> automaton) {
		return new InvertedAutomaton<V, E>() {
			@Override
			public Automaton<V, E> delegate() {
				return automaton;
			}
		};
	}

	public static <V, E> Automaton<ImmutableSet<V>, E> deterministic(Automaton<V, E> nonDeterministic) {
		return null;
	}

	public static <V, E> Automaton<V, E> create() {
		return GraphAutomaton.create();
	}

	public static <V, E> Automaton<V, E> create(Automaton<? extends V, ? extends E> prototype) {
		Automaton<V, E> automaton = GraphAutomaton.create();
		automaton.addAll(prototype);
		return automaton;
	}

	public static <V_OLD, E, V_NEW> Automaton<V_NEW, E> transformVertices(
			Automaton<? extends V_OLD, ? extends E> oldAutomaton,
			Function<? super V_OLD, ? extends V_NEW> vertexFunction
		) {
		return transform(oldAutomaton, vertexFunction, Functions.<E>identity());
	}

	public static <V, E_OLD, E_NEW> Automaton<V, E_NEW> transformEdgeLabels(
			Automaton<? extends V, ? extends E_OLD> oldAutomaton,
			Function<? super E_OLD, ? extends E_NEW> edgeLabelFunction
		) {
		return transform(oldAutomaton, Functions.<V>identity(), edgeLabelFunction);
	}

	public static <V_OLD, E_OLD, V_NEW, E_NEW> Automaton<V_NEW, E_NEW> transform(
			Automaton<? extends V_OLD, ? extends E_OLD> oldAutomaton,
			Function<? super V_OLD, ? extends V_NEW> vertexFunction,
			Function<? super E_OLD, ? extends E_NEW> edgeLabelFunction
		) {
		Automaton<V_NEW, E_NEW> newAutomaton = GraphAutomaton.create();
		transform(oldAutomaton, newAutomaton, vertexFunction, edgeLabelFunction);
		return newAutomaton;
	}

	public static <V_OLD, E_OLD, V_NEW, E_NEW> void transform(
			Automaton<? extends V_OLD, ? extends E_OLD> oldAutomaton,
			Automaton<? super V_NEW, ? super E_NEW> newAutomaton,
			Function<? super V_OLD, ? extends V_NEW> vertexFunction,
			Function<? super E_OLD, ? extends E_NEW> edgeLabelFunction
		) {
		Graphs.transform(oldAutomaton, newAutomaton, vertexFunction, edgeLabelFunction);
		
		for (V_OLD oldStartVertex : oldAutomaton.getStartVertices()) {
			V_NEW newStartVertex = vertexFunction.apply(oldStartVertex);
			newAutomaton.addStartVertex(newStartVertex);
		}
		
		for (V_OLD oldAcceptVertex : oldAutomaton.getAcceptVertices()) {
			V_NEW newAcceptVertex = vertexFunction.apply(oldAcceptVertex);
			newAutomaton.addAcceptVertex(newAcceptVertex);
		}
		
		for (V_OLD oldRejectVertex : oldAutomaton.getRejectVertices()) {
			V_NEW newRejectVertex = vertexFunction.apply(oldRejectVertex);
			newAutomaton.addRejectVertex(newRejectVertex);
		}
	}

	public static <V, E> Collection<Path<V, E>> findPaths(Automaton<V, E> automaton) {
		if (automaton.vertices().size() > 5) {
			System.out.print("");
		}
		
		Collection<Path<V, E>> paths = Sets.newHashSet();
		
		for (V startVertex : automaton.getStartVertices()) {
			paths.addAll(findPaths(automaton, startVertex, Path.<V, E>create(startVertex), Sets.<V>newHashSet()));
		}
		
		return paths;
	}

	private static <V, E> Collection<? extends Path<V, E>> findPaths(Automaton<V, E> automaton, V current, Path<V, E> currentPath, Collection<V> visited) {
		// TODO handle reject vertices
		
		if (!visited.add(current)) {
			return Collections.emptyList();
		}
		
		Collection<Path<V, E>> paths = Sets.newHashSet();
		
		if (automaton.getAcceptVertices().contains(current)) {
			paths.add(currentPath);
		}
		
		for (Graph.Edge<V, E> edge : automaton.outboundEdges(current)) {
			for (Path<V, E> subPath : findPaths(automaton, edge.opposite(current), currentPath.appendEdge(edge), visited)) {
				paths.add(subPath);
			}
		}
		
		return paths;
	}

}
